Corso di Laurea in Informatica Linguaggio e Metodi della Matematica: Prova scritta del 9 settembre 2002

COGNOME E NOME

MATRICOLA  CORSO  AULA

Firma

NOTA: Le risposte vanno giustificate.

Esercizio 1. Trascrivere la seguente formula in linguaggio naturale e scriverne una sua forma normale prenessa:

[∃a∃b(ax + by = z)] → {∀d[(∃a(da = x)) ∧ (∃a(da = y)) → (∃a(da = z))]}.

Soluzione: Se z è somma di un multiplo di x ed un multiplo di y, allora ogni divisore comune di x ed y divide anche z.

∀a, b∀d, a_{1}, a_{2}∃a_{3}(ax + by = z → (da_{1} = x ∧ da_{2} = y → da_{3} = z))

Esercizio 2. Formalizzare, usando le notazioni logiche e la notazione x ∈ A, l’espressione:

“Se A è sottoinsieme di B allora C − B è sottoinsieme di C − A”.

Soluzione: ∀x(x ∈ A → x ∈ B) → ∀y(y ∈ C ∧ y ∉ B → y ∈ C ∧ y ∉ A).

Esercizio 3. Sia f : ℝ → ℝ la funzione definita da f(x) = x^{3} + x^{2} per ogni x ∈ ℝ e sia g : ℤ → ℤ la funzione definita da g(x) = x^{3} + x^{2} per ogni x ∈ ℤ (pur avendo la stessa formula, le funzioni f e g si distinguono per avere dominio e codominio diversi). Stabilire se le funzioni f e g sono iniettive e/o surgettive.

Soluzione: f non è iniettiva perché f(0) = 0 = f(1). g non è iniettiva per lo stesso motivo. f è surgettiva perchè è una funzione continua sui reali che assume valori arbitrariamente grandi sia positivi che negativi. g non è surgettiva in quanto ad esempio non assume mai il valore 3. Se infatti g(x) = x^{3} + x^{2} = x^{2}(x + 1) = 3, con x intero, x dovrebbe dividere 3, e pertanto le uniche possibilità sarebbero x = 1, x = −1, x = 3, x = −3, ma nessuno di questi valori dà g(x) = 3.

Esercizio 4. Consideriamo le parole di lunghezza 8 composte da lettere dell’alfabeto italiano (21 lettere).

1. Quante sono le parole che non contengono né la lettera a né la lettera b?

2. Quante sono le parole che contengono la lettera a ma non la lettera b?

3. Quante sono le parole che contengono sia la lettera a che la lettera b?

Soluzione: (1) 19^{8}.

(2) 20^{8} − 19^{8} (conto quelle che non contengono la b e sottraggo il numero di quelle che non contengono nemmeno la a).

(3) 21^{8} − 2 · 20^{8} + 19^{8}. Il numero totale delle parole è 21^{8}. Da queste sottraggo l’unione di quelle che non contengono la a, che sono 20^{8}, e di quelle che non contengono la b che sono altrettante. Applicando la formula per la cardinalità dell’unione (formula di inclusione-esclusione) si ottiene il risultato desiderato osservando che 19^{8} è il numero della parole che non contengono nè la a nè la b.

Esercizio 5. Determinare per quali valori di a esiste una soluzione al seguente sistema:

\{ \begin{matrix}x ≡ 5 (mod 77) \\ y ≡ 4 (mod 91) \\ x + y = a \end{matrix}

e determinare una soluzione per a = 23.

Soluzione: Le soluzioni sono della forma x = 5 + 77k, y = 4 + 91s, x + y = 9 + 77k + 91s = a. I numeri della forma 77k + 91s sono esattamente i multipli di 7, essendo 7 = 6 · 77 − 5 · 91 il massimo comun divisore tra 77 e 91. Quindi il sistema ha soluzione per a della forma 9 + m7. Per a = 23 = 9 + 2 · 7 = 9 + 12 · 77 − 10 · 91, otteniamo la soluzione x = 5 + 77 · 12, y = 4 − 10 · 91.

Esercizio 6. Definiamo per ricorrenza la successione f_{n} ponendo f_{0} = 0, f_{n+1} = f_{n}^{2}−n; determinare N tale che la seguente formula

∀n(n ≥ N → f_{n} > 2^{n})

sia vera per i numeri naturali, e dimostrarla.

Soluzione: f_{0} = 0, f_{1} = 0, f_{2} = −1, f_{3} = −1, f_{4} = −2, f_{5} = 0, f_{6} = −5, f_{7} = 19, f_{8} = 19^{2} − 7 > 2^{8}. Per n = N = 8 vale dunque la formula f_{n+1} > 2^{n}. Per verificare che la formula continua a valere per ogni n ≥ N consideriamo un tale n e supponiamo per ipotesi induttiva che f_{n} > 2^{n}. Si ha allora f_{n+1} = f_{n}^{2} − n > (2^{n})^{2} − n ≥ 2^{n+1}, da cui la tesi.

COGNOME E NOME

MATRICOLA  CORSO  AULA

Firma

NOTA: Le risposte vanno giustificate.

Esercizio 1. Trascrivere la seguente formula in linguaggio naturale e scriverne una sua forma normale prenessa:

{∀d[(∃a(da = x)) ∧ (∃a(da = y)) → (∃a(da = z))]} → [∃a∃b(ax + by = z)].

Esercizio 2. Formalizzare, usando le notazioni logiche e la notazione x ∈ A, l’espressione:

“Se A è sottoinsieme di B allora C − B è sottoinsieme di C − A”.

Esercizio 3. Sia f : ℝ → ℝ la funzione definita da f(x) = x^{3} +x^{2} per ogni x ∈ ℝ e sia g : ℤ → ℤ la funzione definita da f(x) = x^{3} + x^{2} per ogni x ∈ ℤ (pur avendo la stessa formula, le funzioni f e g si distinguono per avere dominio e codominio diversi). Stabilire se le funzioni f e g sono iniettive e/o surgettive. La funzione 2x^{3}−x^{2} iniettiva-surgettiva come funzione ℤ → ℤ? Come funzione ℝ → ℝ?

Esercizio 4. Consideriamo le parole di lunghezza 7 composte da lettere dell’alfabeto inglese (26 lettere).

1. Quante sono le parole che non contengono né la lettera a né la lettera b?

2. Quante sono le parole che contengono la lettera a ma non la lettera b?

3. Quante sono le parole che contengono sia la lettera a che la lettera b?

Esercizio 5. Determinare per quali valori di a esiste una soluzione al seguente sistema:

\{ \begin{matrix}x ≡ 3 (mod 55) \\ y ≡ 6 (mod 121) \\ x + y = a \end{matrix}

e determinare una soluzione per a = 31.

Esercizio 6. Definiamo per ricorrenza la successione f_{n} ponendo f_{0} = 1, f_{n+1} = f_{n}^{2}−n; determinare N tale che la seguente formula

∀n(n ≥ N → f_{n} > 2^{n})

COGNOME E NOME

MATRICOLA  CORSO  AULA

Firma

NOTA: Le risposte vanno giustificate.

Esercizio 1. Trascrivere la seguente formula in linguaggio naturale e scriverne una sua forma normale prenessa:

[∃a∃b(ax + by = z)] → {∀d[(∃a(da = x)) ∧ (∃a(da = y)) → (∃a(da = z))]}.

Esercizio 2. Formalizzare, usando le notazioni logiche e la notazione x ∈ A, l’espressione:

“Se A è sottoinsieme di B allora C − B è sottoinsieme di C − A”.

Esercizio 3. Sia f : ℝ → ℝ la funzione definita da f(x) = x^{3} + x^{2} per ogni x ∈ ℝ e sia g : ℤ → ℤ la funzione definita da f(x) = x^{3} + x^{2} per ogni x ∈ ℤ (pur avendo la stessa formula, le funzioni f e g si distinguono per avere dominio e codominio diversi). Stabilire se le funzioni f e g sono iniettive e/o surgettive.

Esercizio 4. Consideriamo le parole di lunghezza 9 composte da lettere dell’alfabeto italiano (21 lettere).

1. Quante sono le parole che non contengono né la lettera a né la lettera b?

2. Quante sono le parole che contengono la lettera a ma non la lettera b?

3. Quante sono le parole che contengono sia la lettera a che la lettera b?

Esercizio 5. Determinare per quali valori di a esiste una soluzione al seguente sistema:

\{ \begin{matrix}x ≡ 8 (mod 65) \\ y ≡ 2 (mod 104) \\ x + y = a \end{matrix}

e determinare una soluzione per a = 36.

Esercizio 6. Definiamo per ricorrenza la successione f_{n} ponendo f_{0} = 0, f_{n+1} = f_{n}^{2} − 2n; determinare N tale che la seguente formula

∀n(n ≥ N → f_{n} > 2^{n})

COGNOME E NOME

MATRICOLA  CORSO  AULA

Firma

NOTA: Le risposte vanno giustificate.

Esercizio 1. Trascrivere la seguente formula in linguaggio naturale e scriverne una sua forma normale prenessa:

{∀d[(∃a(da = x)) ∧ (∃a(da = y)) → (∃a(da = z))]} → [∃a∃b(ax + by = z)].

Esercizio 2. Formalizzare, usando le notazioni logiche e la notazione x ∈ A, l’espressione:

“Se A è sottoinsieme di B allora C − B è sottoinsieme di C − A”.

Esercizio 3. Sia f : ℝ → ℝ la funzione definita da f(x) = x^{3} + x^{2} per ogni x ∈ ℝ e sia g : ℤ → ℤ la funzione definita da f(x) = x^{3} + x^{2} per ogni x ∈ ℤ (pur avendo la stessa formula, le funzioni f e g si distinguono per avere dominio e codominio diversi). Stabilire se le funzioni f e g sono iniettive e/o surgettive.

Esercizio 4. Consideriamo le parole di lunghezza 8 composte da lettere dell’alfabeto inglese (26 lettere).

1. Quante sono le parole che non contengono né la lettera a né la lettera b?

2. Quante sono le parole che contengono la lettera a ma non la lettera b?

3. Quante sono le parole che contengono sia la lettera a che la lettera b?

Esercizio 5. Determinare per quali valori di a esiste una soluzione al seguente sistema:

\{ \begin{matrix}x ≡ 7 (mod 63) \\ y ≡ 6 (mod 98) \\ x + y = a \end{matrix}

e determinare una soluzione per a = 83.

Esercizio 6. Definiamo per ricorrenza la successione f_{n} ponendo f_{0} = 1, f_{n+1} = f_{n}^{2} − 3n; determinare N tale che la seguente formula

∀n(n ≥ N → f_{n} > 2^{n})